"""
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        r = []
        node = self
        while node:
            r.append(str(node.val))
            node = node.next
        return "->".join(r)


class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return head
        size = 0
        tmp = head
        while tmp:
            tmp = tmp.next
            size += 1
        if k % size == 0:
            return head
        tmp = head
        k = size - k % size
        while k > 1:
            tmp = tmp.next
            k -= 1
        cur = tmp.next
        tmp.next = None
        res = cur
        while cur and cur.next:
            cur = cur.next
        cur.next = head
        return res


if __name__ == '__main__':
    tree = ListNode(0)
    tree.next = ListNode(1)
    tree.next.next = ListNode(2)
    print(tree)
    s = Solution()
    print(s.rotateRight(tree, 4))
